﻿/* Write a program that finds the sequence of maximal sum in given array. Example:
	{2, 3, -6, -1, 2, -1, 6, 4, -8, 8}  {2, -1, 6, 4}
	Can you do it with only one loop (with single scan through the elements of the array)? */

using System;

namespace MaxSequenceSum
{
    class MaxSequenceSum
    {
        static void Main()
        {
            int bestStart = 0;
            int currStart = 0;
            int currSum = 0;
            int bestSum = 0;

            int[] testArray = { 2, 3, -6, -1, 2, -1, 6, 4, -8, 8 }; //initializing the array

            for (int i = 0; i < testArray.Length; i++)  //serching for the maxim sum in the elements of the array & the start position
            {
                if (currSum == 0)
                {
                    currStart = i;
                }
                currSum += testArray[i];

                if (currSum < 0)
                {
                    currSum = 0;
                }

                if (currSum > bestSum)
                {
                    bestSum = currSum;
                    bestStart = currStart;
                }
            }

            Console.WriteLine("Our Sequence of Maximal Sum in the array start from index {0} and have sum {1}", bestStart, bestSum);        //print the result
        }
    }
}
